Maximization Problems in Single Machine Scheduling
Identifieur interne : 006B74 ( Main/Exploration ); précédent : 006B73; suivant : 006B75Maximization Problems in Single Machine Scheduling
Auteurs : Mohamed Ali Aloulou [France] ; Mikhail Y. Kovalyov [Biélorussie] ; Marie-Claude Portmann [France]Source :
- Annals of Operations Research [ 0254-5330 ] ; 2004-07-01.
Descripteurs français
- mix :
English descriptors
- KwdEn :
Abstract
Abstract: Problems of scheduling n jobs on a single machine to maximize regular objective functions are studied. Precedence constraints may be given on the set of jobs and the jobs may have different release times. Schedules of interest are only those for which the jobs cannot be shifted to start earlier without changing job sequence or violating release times or precedence constraints. Solutions to the maximization problems provide an information about how poorly such schedules can perform. The most general problem of maximizing maximum cost is shown to be reducible to n similar problems of scheduling n−1 jobs available at the same time. It is solved in O(mn+n 2) time, where m is the number of arcs in the precedence graph. When all release times are equal to zero, the problem of maximizing the total weighted completion time or the weighted number of late jobs is equivalent to its minimization counterpart with precedence constraints reversed with respect to the original ones. If there are no precedence constraints, the problem of maximizing arbitrary regular function reduces to n similar problems of scheduling n−1 jobs available at the same time.
Url:
DOI: 10.1023/B:ANOR.0000030679.25466.02
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 003873
- to stream Istex, to step Curation: 003830
- to stream Istex, to step Checkpoint: 001783
- to stream Main, to step Merge: 006E78
- to stream Hal, to step Corpus: 003126
- to stream Hal, to step Curation: 003126
- to stream Hal, to step Checkpoint: 004D89
- to stream Main, to step Merge: 007337
- to stream Main, to step Curation: 006B74
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Maximization Problems in Single Machine Scheduling</title><author><name sortKey="Aloulou, Mohamed Ali" sort="Aloulou, Mohamed Ali" uniqKey="Aloulou M" first="Mohamed Ali" last="Aloulou">Mohamed Ali Aloulou</name></author><author><name sortKey="Kovalyov, Mikhail Y" sort="Kovalyov, Mikhail Y" uniqKey="Kovalyov M" first="Mikhail Y." last="Kovalyov">Mikhail Y. Kovalyov</name></author><author><name sortKey="Portmann, Marie Claude" sort="Portmann, Marie Claude" uniqKey="Portmann M" first="Marie-Claude" last="Portmann">Marie-Claude Portmann</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:ECF9012F57586719DD1E43E0F563E2A3D4C46404</idno><date when="2004" year="2004">2004</date><idno type="doi">10.1023/B:ANOR.0000030679.25466.02</idno><idno type="url">https://api.istex.fr/ark:/67375/VQC-2DR902PZ-J/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">003873</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">003873</idno><idno type="wicri:Area/Istex/Curation">003830</idno><idno type="wicri:Area/Istex/Checkpoint">001783</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">001783</idno><idno type="wicri:doubleKey">0254-5330:2004:Aloulou M:maximization:problems:in</idno><idno type="wicri:Area/Main/Merge">006E78</idno><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:inria-00099946</idno><idno type="url">https://hal.inria.fr/inria-00099946</idno><idno type="wicri:Area/Hal/Corpus">003126</idno><idno type="wicri:Area/Hal/Curation">003126</idno><idno type="wicri:Area/Hal/Checkpoint">004D89</idno><idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">004D89</idno><idno type="wicri:doubleKey">0254-5330:2004:Aloulou M:maximization:problems:in</idno><idno type="wicri:Area/Main/Merge">007337</idno><idno type="wicri:Area/Main/Curation">006B74</idno><idno type="wicri:Area/Main/Exploration">006B74</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Maximization Problems in Single Machine Scheduling</title><author><name sortKey="Aloulou, Mohamed Ali" sort="Aloulou, Mohamed Ali" uniqKey="Aloulou M" first="Mohamed Ali" last="Aloulou">Mohamed Ali Aloulou</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>Ecole des Mines de Nancy, Parc de Saurupt, MACSI team of INRIA-Lorraine and LORIA-INPL, 54042, Nancy Cedex</wicri:regionArea><placeName><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region><settlement type="city">Nancy</settlement></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author><author><name sortKey="Kovalyov, Mikhail Y" sort="Kovalyov, Mikhail Y" uniqKey="Kovalyov M" first="Mikhail Y." last="Kovalyov">Mikhail Y. Kovalyov</name><affiliation wicri:level="1"><country xml:lang="fr">Biélorussie</country><wicri:regionArea>Faculty of Economics, Belarus State University, K. Marxa 31, 220050, Minsk</wicri:regionArea><wicri:noRegion>Minsk</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Biélorussie</country></affiliation></author><author><name sortKey="Portmann, Marie Claude" sort="Portmann, Marie Claude" uniqKey="Portmann M" first="Marie-Claude" last="Portmann">Marie-Claude Portmann</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>Ecole des Mines de Nancy, Parc de Saurupt, MACSI team of INRIA-Lorraine and LORIA-INPL, 54042, Nancy Cedex</wicri:regionArea><placeName><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region><settlement type="city">Nancy</settlement></placeName></affiliation></author></analytic><monogr></monogr><series><title level="j">Annals of Operations Research</title><title level="j" type="abbrev">Annals of Operations Research</title><idno type="ISSN">0254-5330</idno><idno type="eISSN">1572-9338</idno><imprint><publisher>Kluwer Academic Publishers</publisher><pubPlace>Boston</pubPlace><date type="published" when="2004-07-01">2004-07-01</date><biblScope unit="volume">129</biblScope><biblScope unit="issue">1-4</biblScope><biblScope unit="page" from="21">21</biblScope><biblScope unit="page" to="32">32</biblScope></imprint><idno type="ISSN">0254-5330</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0254-5330</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>maximization problem</term><term>precedence constraints</term><term>release times</term><term>scheduling</term><term>semi-active schedules</term></keywords><keywords scheme="mix" xml:lang="fr"><term>contraintes de précédence</term><term>dates de disponibilité</term><term>flexibilité</term><term>maximization problems</term><term>ordonnancement</term><term>precedence constraints</term><term>problème de maximisation</term><term>release times</term><term>schedule flexibility</term><term>scheduling</term><term>single machine</term><term>une machine</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: Problems of scheduling n jobs on a single machine to maximize regular objective functions are studied. Precedence constraints may be given on the set of jobs and the jobs may have different release times. Schedules of interest are only those for which the jobs cannot be shifted to start earlier without changing job sequence or violating release times or precedence constraints. Solutions to the maximization problems provide an information about how poorly such schedules can perform. The most general problem of maximizing maximum cost is shown to be reducible to n similar problems of scheduling n−1 jobs available at the same time. It is solved in O(mn+n 2) time, where m is the number of arcs in the precedence graph. When all release times are equal to zero, the problem of maximizing the total weighted completion time or the weighted number of late jobs is equivalent to its minimization counterpart with precedence constraints reversed with respect to the original ones. If there are no precedence constraints, the problem of maximizing arbitrary regular function reduces to n similar problems of scheduling n−1 jobs available at the same time.</div></front></TEI><affiliations><list><country><li>Biélorussie</li><li>France</li></country><region><li>Grand Est</li><li>Lorraine (région)</li></region><settlement><li>Nancy</li></settlement></list><tree><country name="France"><region name="Grand Est"><name sortKey="Aloulou, Mohamed Ali" sort="Aloulou, Mohamed Ali" uniqKey="Aloulou M" first="Mohamed Ali" last="Aloulou">Mohamed Ali Aloulou</name></region><name sortKey="Aloulou, Mohamed Ali" sort="Aloulou, Mohamed Ali" uniqKey="Aloulou M" first="Mohamed Ali" last="Aloulou">Mohamed Ali Aloulou</name><name sortKey="Portmann, Marie Claude" sort="Portmann, Marie Claude" uniqKey="Portmann M" first="Marie-Claude" last="Portmann">Marie-Claude Portmann</name></country><country name="Biélorussie"><noRegion><name sortKey="Kovalyov, Mikhail Y" sort="Kovalyov, Mikhail Y" uniqKey="Kovalyov M" first="Mikhail Y." last="Kovalyov">Mikhail Y. Kovalyov</name></noRegion><name sortKey="Kovalyov, Mikhail Y" sort="Kovalyov, Mikhail Y" uniqKey="Kovalyov M" first="Mikhail Y." last="Kovalyov">Mikhail Y. Kovalyov</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 006B74 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 006B74 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:ECF9012F57586719DD1E43E0F563E2A3D4C46404
|texte= Maximization Problems in Single Machine Scheduling
}}
| This area was generated with Dilib version V0.6.33. |  |